

/**
 * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，
 * 写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
 *
 * 链接：https://leetcode-cn.com/problems/binary-search
 *
 * @date 2021-11-16
 * @author X.
 *
 * Solution:
 * binary search
 * 时间复杂度：O(logN),空间复杂度O(1)
 *
 */
public class BinarySearch704 {

    // binary search
    public static int search(int[] nums, int target) {
        int left = 0;
        int right  = nums.length - 1;
        while (left <= right) {
            int half = (right - left)/2 + left;
            if (nums[half] == target) {
                return half;
            } else if (nums[half] < target) {
                left = half + 1;
            } else {
                right = half - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {-1,0,3,5,9,12};
        int target = 2;

        int res = search(nums, target);
        System.out.println("res = " + res);
    }
}
